/**
 * 题目：前往目标的最小代价
 * 给你一个数组 start ，其中 start = [startX, startY] 表示你的初始位置位于二维空间上的 (startX, startY) 。另给你一个数组 target ，其中 target = [targetX, targetY] 表示你的目标位置 (targetX, targetY) 。
 *
 * 从位置 (x1, y1) 到空间中任一其他位置 (x2, y2) 的代价是 |x2 - x1| + |y2 - y1| 。
 *
 * 给你一个二维数组 specialRoads ，表示空间中存在的一些特殊路径。其中 specialRoads[i] = [x1i, y1i, x2i, y2i, costi] 表示第 i 条特殊路径可以从 (x1i, y1i) 到 (x2i, y2i) ，但成本等于 costi 。你可以使用每条特殊路径任意次数。
 *
 * 返回从 (startX, startY) 到 (targetX, targetY) 所需的最小代价。
 * https://leetcode.cn/problems/minimum-cost-of-a-path-with-special-roads/description/
 */

public class MinimumCost {
    static final Integer INF = Integer.MAX_VALUE;
    public int minimumCost(int[] start, int[] target, int[][] specialRoads) {
        long startXoy = ((long) start[0] << 32) | (start[1]);
        long targetXoy = ((long) target[0] << 32) | (target[1]);

        // 从起点到其他点的最短路径
        Map<Long, Integer> dist = new HashMap<>();
        dist.put(targetXoy, INF);                   // 到终点的距离为 无限远
        dist.put(startXoy, 0);                      // 到起点的距离为 0

        HashSet<Long> vis = new HashSet<>();        // 哪些点已经确定了最短路径
        while (true) {
            // 先选出一个最短路径
            Set<Map.Entry<Long, Integer>> entrySet = dist.entrySet();
            int min = INF;
            Long chosenXoy = -1L;
            for (Map.Entry<Long, Integer> entry : entrySet) {
                Long key = entry.getKey();
                Integer value = entry.getValue();
                // 还没确定的最短路径, 并且 要选出最短路径
                if (!vis.contains(key) && value < min) {
                    chosenXoy = key;                // 更新坐标
                    min = value;                    // 更新最短路径
                }
            }

            // 有新结点被确定为最短路径
            vis.add(chosenXoy);
            if (chosenXoy == targetXoy)
                return min;
            // 更新到终点的最短路径
            int x = (int) (chosenXoy >> 32), y = (int) (chosenXoy & INF);
            dist.merge(targetXoy, min + Math.abs(x - target[0]) + Math.abs(y - target[1]),
                    (Integer a, Integer b) -> { return Math.min(a, b); });
            // 然后以这个新的最短路径为结点, 开始 “扩散“
            for (int[] cur : specialRoads) {
                // 走这条路：到 传送门的距离 + cost
                int weight = min + Math.abs(x - cur[0]) + Math.abs(y - cur[1]) + cur[4];
                // 走这个路之后 的点
                long nextXoy = ((long) cur[2] << 32) | cur[3];
                // 可以可以尽量更短
                if (weight < dist.getOrDefault(nextXoy, INF)) {
                    dist.put(nextXoy, weight);
                }
            }
        }
    }
}
